package leetcode.f1t100;

/**
 * 从单词1变化到单词二, 只允许做新增修改删除单个字符操作,最少要几步
 * https://leetcode.com/problems/edit-distance/
 *
 * @Author lichongxiao
 * @Date 2022/11/23 16:49
 */
public class Q72_EditDistance {

    public static void main(String[] args) {
        Q72_EditDistance bean = new Q72_EditDistance();
        System.out.println(bean.minDistance("horse", "ros"));
    }

    public int minDistance(String word1, String word2) {
        char[] chars1 = word1.toCharArray(), chars2 = word2.toCharArray();
        return processDp(chars1, chars2);
    }

    // 构造一个函数，返回chars1[i~chars1.length]变成chars2[j~chars2.length]最少需要的步数
    private int processRecursion(char[] chars1, char[] chars2, int i, int j) {
        // 若chars1已经没有字符了，chars2剩下的字符都需要做插入操作
        if (i == chars1.length) {
            return chars2.length - j;
        }
        // 若chars2已经没有字符了，chars1剩下的字符都需要做删除操作
        if (j == chars2.length) {
            return chars1.length - i;
        }
        int p1 = Integer.MAX_VALUE;
        // 当前两个字符相等，不需要变换，直接往后移动
        if (chars1[i] == chars2[j]) {
            p1 = processRecursion(chars1, chars2, i + 1, j + 1);
        }
        // 删除i处的字符
        int p2 = processRecursion(chars1, chars2, i + 1, j) + 1;
        // 替换i处的字符
        int p3 = processRecursion(chars1, chars2, i + 1, j + 1) + 1;
        // 插入一个字符到i位置之前对应j位置的字符
        int p4 = processRecursion(chars1, chars2, i, j + 1) + 1;
        // 返回所有情况下最小的值
        return Math.min(p1, Math.min(p2, Math.min(p3, p4)));

    }

    // 构造一个函数，返回chars1[i~chars1.length]变成chars2[j~chars2.length]最少需要的步数
    private int processCache(char[] chars1, char[] chars2, int i, int j, int[][] cache) {
        if (cache[i][j] != 0) {
            return cache[i][j];
        }
        // 若chars1已经没有字符了，chars2剩下的字符都需要做插入操作
        if (i == chars1.length) {
            cache[i][j] = chars2.length - j;
            return cache[i][j];
        }
        // 若chars2已经没有字符了，chars1剩下的字符都需要做删除操作
        if (j == chars2.length) {
            cache[i][j] = chars1.length - i;
            return cache[i][j];
        }
        int p1 = Integer.MAX_VALUE;
        // 当前两个字符相等，不需要变换，直接往后移动
        if (chars1[i] == chars2[j]) {
            p1 = processRecursion(chars1, chars2, i + 1, j + 1);
        }
        // 删除i处的字符
        int p2 = processRecursion(chars1, chars2, i + 1, j) + 1;
        // 替换i处的字符
        int p3 = processRecursion(chars1, chars2, i + 1, j + 1) + 1;
        // 插入一个字符到i位置之前对应j位置的字符
        int p4 = processRecursion(chars1, chars2, i, j + 1) + 1;
        // 返回所有情况下最小的值
        cache[i][j] = Math.min(p1, Math.min(p2, Math.min(p3, p4)));
        return cache[i][j];
    }

    private int processDp(char[] chars1, char[] chars2) {
        int[][] dp = new int[chars1.length + 1][chars2.length + 1];

        // 若chars2已经没有字符了，chars1剩下的字符都需要做删除操作
        for (int i = 0; i < chars1.length; i++) {
            dp[i][chars2.length] = chars1.length - i;
        }
        // 若chars1已经没有字符了，chars2剩下的字符都需要做插入操作
        for (int j = 0; j <= chars2.length; j++) {
            dp[chars1.length][j] = chars2.length - j;
        }

        for (int i = chars1.length - 1; i >= 0; i--) {
            for (int j = chars2.length - 1; j >= 0; j--) {
                // 当前两个字符相等，不需要变换，直接往后移动
                if (chars1[i] == chars2[j]) {
                    dp[i][j] = dp[i + 1][j + 1];
                    continue;
                }
                dp[i][j] = (
                        dp[i + 1][j] > dp[i + 1][j + 1]
                                ? (dp[i + 1][j + 1] > dp[i][j + 1] ? dp[i][j + 1] : dp[i + 1][j + 1])
                                : (dp[i + 1][j] > dp[i][j + 1] ? dp[i][j + 1] : dp[i + 1][j])
                ) + 1;
//                // 删除i处的字符
//                int p2 = dp[i + 1][j] + 1;
//                // 替换i处的字符
//                int p3 = dp[i + 1][j + 1] + 1;
//                // 插入一个字符到i位置之前对应j位置的字符
//                int p4 = dp[i][j + 1] + 1;
//                // 返回所有情况下最小的值
//                dp[i][j] = Math.min(p2, Math.min(p3, p4));
            }
        }
        return dp[0][0];
    }
}
